1. Field of the Invention
The present invention relates to the field of network management and more particularly to a method of deducing the state of network links from sequentially received distance-vector routing updates and/or from a sequence of routing table updates and a network management system performing the method.
2. Discussion of Related Art
The internet is a packet-switched network comprising numerous routers and links between the routers. In packet-switched networks, information to be carried is split up into packets, which may take different routes across a network from a sender to a receiver, and such networks are now increasingly used to carry telephony-type information, e.g., voice or video information. Timely localization of faulty components (e.g., broken links, failed router interfaces) remains one of the most important problems in network management while instrumenting and monitoring every single component is infeasible. Network management systems need to obtain reliable and up-to-date information about the states of network links (e.g., broken links, failed router interfaces) in order to monitor the health of the network and to perform root-cause-analysis. Soft-failures of links (e.g., link cost increase) are hard or expensive to detect.
There are two major classes of routing protocols used in packet-switched networks: Distance-vector routing protocols and Link-state routing protocols. Distance-vector routing protocols (e.g., EIGRP, AODV, DSDV, RIP, RTMP) are simple and efficient in fairly small environments, and require little, if any configuration and management (unlike link state protocols).
A distance vector routing protocol can best be understood by recalling the meaning of the word vector. A vector is a number with two components: magnitude and direction. In a network, a vector is said to have “cost” and direction or distance and direction.
In a distance vector protocol, neighboring routers (e.g., routers connected to the same subnetwork) exchange tables of routing vectors. Routers following a typical distance vector routing protocol periodically send routing updates to all neighboring routers by broadcasting their entire routing tables. The routing tables are lists of distance vectors, each distance vector consisting of entries in the form <destination, distance, direction>, where distance is defined in terms of a metric (e.g., hop count) and direction is defined in terms of specifying a next-hop (neighboring) router. Each router pulls from its routing table a list of all known subnetworks, and some metric relating the goodness or “cost” of the path to that subnetwork. This information is transmitted to all neighboring routers.
Each link e in the network may have an associated cost denoted by cost(e). The cost of a route from source node s to destination node d denoted cost(s, d) is the sum of the costs of all links on the route from s to d. If all links on a route have cost 1, the cost of the route is simply the number of links (hops) along the route. A distance vector in a table received by router s minimally includes the following parameters: <d, a, c> and indicates that from the perspective of s, the next hop on the shortest route from s to d is router a, denoted as next-hop(s, d)=a, and the cost of the shortest route from router s to router a is c.
Upon receiving an updated distance vector from a neighboring router, the router implementing a distance vector routing protocol begins the process of updating its own (local) routing table. For each subnetwork listed in a received routing table, the router extracts the cost information from the received routing table and adds to it the cost of the link from the neighbor that sent the received routing table to the receiving router. The receiving router then examines the current (local) routing table to determine if the subnetwork is listed and if it is, the cost to reach that network using the current route. If the subnetwork is not listed in the table, the routing protocol adds the new subnetwork including the port on which the update was received and the address of the router that sent the update. This router is the best known path to the new subnetwork.
If the subnetwork already appears in the table, the routing protocol compares the current cost to the cost it calculated via the updating router. If the router that transmitted the updated (received) routing table is reporting a lower cost route, the routing protocol updates the routing table entry for that subnetwork with the new router's address, the port on which the update was received, and the newly calculated cost. The router that transmitted the update now represents the best known route to the indicated subnetwork.
For example, a received routing table may include a distance vector indicating that “Destination A is 5 hops away (from neighboring g router), in the direction of next-hop router X.” When the receiving router receives that distance vector from its neighbor, it determines whether its cost of reaching any destination would decrease if packets to that destination were to be sent through that neighbor. If so, the router updates its own distance vector. Thus each router learns better (less costly) routes from its neighboring routers' perspectives, and then advertises the best routes from its own perspective, thus propagating the updated distance vectors. Alternatively, if a link is severed (hard failure) or its link cost increases (soft failure) a router directly connected to that link detects the change, and then transmits a routing table including distance vectors indicating an increased cost from its own perspective, thus propagating the updated distance vectors. It should be noted that it is not essential for a distance vector routing protocol to transmit its updates periodically. The updates can be transmitted only in the event of a change. Newer distance vector routing protocols take this approach.
In a link state routing protocol, the changes to the link state is readily available. On the other hand, the routing events in a distance vector protocol (routing table updates) broadcast only the length of the shortest path from a node s to node d but do not explicitly include changes to the link state.
The Simple Network Management Protocol (SNMP) defines a standard by which a remote user can view or change management information for a networked device (a host, gateway, router, server, etc.). A monitoring or management application on the remote user's system uses the SNMP protocol to communicate with an SNMP agent on the device to access the network management data. The SNMP agent on each device can provide information about the device's network configuration and operations, such as the device's network interfaces, routing tables, IP packets sent and received, and IP packets lost. This information, called SNMP objects, is stored in a standard format defined in the Management Information Base (MIB). The SNMP protocol, together with the MIB, provide a standard way to view and change network management information on devices from different vendors. The MIB defines the SNMP objects that can be managed and the format for each object. Any application that implements SNMP can access MIB data on a specified device. SNMP traps enable an agent to notify the management station of significant events by way of an unsolicited SNMP message.
Directed acyclic graphs, called “dags”, are an important class of graphs, being part “tree”, part graph, and having many applications. Using dags, many problems in graphs become simpler to analyze and solve. In the context of a network topology, a directed acyclic graph (DAG) shows all the routes originating from a source node s. The dag(s) is constructed as a minimum weight spanning tree rooted at s. Every router in the network topology is a vertex in dag(s).
A directed acyclic graph has no directed cycles; that is, for any vertex v, there is no nonempty directed path that starts and ends on v. DAGs are used as models where it doesn't make sense for a vertex to have a path to itself. Every directed acyclic graph has a topological sort, an ordering of the vertices such that each vertex comes before all vertices it has edges to. Informally speaking, a DAG “flows” in a single direction, e.g., from source node s to destination node d. Each directed acyclic graph gives rise to a partial order≦on its vertices, where u≦v exactly when there exists a directed path from u to v in the DAG. For every router d in the network topology dag(s), we add a directed edge (nextHop(d, s), d) to dag(s), where nextHop(d, s) denotes the next hop from node d towards node s.